1. Field of the Invention
The present invention relates generally to network computing, data transmission, Gigabit Ethernet, high speed data transmission, high speed networking, data coding and encoding, data assembly and formatting, cluster computers, parallel processing computers, InfiniBand networks, high performance computing, supercomputing and, in particular, to delay optimization, electrical and crossbar switches, and scheduling.
2. Description of Related Art
FIG. 1 shows a prior art data crossbar switch scheduling structure. The scheduling structure includes a control broadcast network 100 and partial schedulers 102 in each line card that separately control the operation of each line card on the basis of global control information. There are a number of pairs of ingress line cards 104 and egress line cards 106 equal to the number of ports on the data crossbar switch 108. The control broadcast network 100 broadcasts requests from the ingress half 104 of each line card to the partial schedulers 102 of all the other line cards.
In operation of the scheduling structure of FIG. 1, each line card can calculate, based on received requests, which line card its ingress half should send to and which line card its egress half should receive from, at any given time.
There is a need to improve upon the prior art data scheduling structure in several ways. First, in the prior art scheduling structure, each partial scheduler must have a control input port for receiving requests (control information) from every other line card on the switch. Therefore, the total number of control input ports for the whole switching fabric scales as n2. For low numbers of line cards (e.g., 8 or less), the number of control input ports is manageable (e.g., 64 or less). However, for switching fabrics with high port counts (e.g., 32 or 64), the number of control input ports scales dramatically (e.g., to 1,024 or 4,096), drastically increasing the cost of the overall switching fabric. Second, in the prior art scheduling structure, the control broadcast network must replicate the control information from each ingress line card half to every other line card half. This replication operation also results in O(N2) scaling of the number of outputs of the control broadcast network and O(N) scaling of the replication factor for each input port's information, which becomes extremely difficult to implement as the number of switch ports is increased. Third, in the prior art scheduling structure, each partial scheduler must receive a separate control request from each ingress line card half. Each request is packed and transmitted as a packet generated by the ingress card half and received by each partial scheduler. Because each packet has some per-packet overhead, for packet framing and error correction and because the ratio of this overhead to useful request payload information decreases with larger requests, the overhead could be reduced by aggregating requests together, such that each partial scheduler only needs to receive fewer individual packets containing request information.
There is a need for scalability to large systems, such as 32 or 64 line cards that require 1,024 or 4,096 control ports in conventional switches. There is a need for there is a need for scalability of broadcast network replication operations and network outputs and there is a need to reduce per-packet overhead.